Packet-switched networks are used to provide an ever-increasing amount of today's varied forms of communication. In addition to computer-to-computer communication via networks such as the Internet, packet-switched networks enable the communication of information associated with other applications such as television, telephone, and radio. Through these and other applications, end users may transmit and receive a multitude of information types over great distances.
In order to move such information from its source to its destination, packet-switched networks employ a number of interconnected routing devices. When one router receives a packet of data, the router will determine where the packet's destination is located and forward the packet to the next closest router. This next router will follow a similar procedure and, in this manner, the packet will eventually be delivered to its destination, much like a “bucket brigade.”
One significant problem in packet switched networks is providing each network with the information necessary to make the determination of which “next hop” router to which each packet should be transmitted. While, in theory, this information could be manually programmed into the router, the size and dynamic nature of network topologies usually render this method impracticable. Instead, various protocols have been developed for automatically determining the best path to each destination for each router. For example, the Open Shortest Path First standard provides for routers within an autonomous system to share information regarding the state of links within the system. Using this information, each router can independently develop a forwarding table for use in determining where each received packet should be sent. When the network state changes, each router updates its forwarding table to ensure that each destination remains reachable and that each path chosen is optimal.